COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	equipment proposal
C00003 00003	\F2\CINTRODUCTION
C00008 00004	\F2\CRESEARCH PROGRAM
C00011 00005	\F2\CVISUAL PERCEPTION
C00020 00006	\F2\CREASONING ABOUT THE PHYSICAL WORLD
C00024 00007	\CRepresentation
C00032 00008	\CGeometric Reasoning
C00037 00009	\CRESEARCH PROGRAM IN ROBOTICS
C00039 00010	\F0\CSensor Technology
C00055 00011	\F2\CACCOMPLISHMENTS
C00064 ENDMK
C⊗;
equipment proposal
add to SDF proposal
  precision machining
  DEC proposal text
  NSF equip proposal
  GM:
  ARPA: ACRONYM, expert systems for IU
  stereo

\F2\CINTRODUCTION



\F0\JWe  describe  a  program  of  research  in  Image Understanding,
robotics,  and artificial intelligence.
Robots combine sensing and perception, planning, and execution.
Our research covers these component areas, with central focus on  intelligent
systems for reasoning about the physical world.

Robotics and  artificial  intelligence  (AI) have  generated  interest  in
fundamental intellectual  problems  of intelligence,  learning,  language,
perception, epistemology, and mathematics. 
Likewise,  IU, robotics  and  AI  have  important  applications. 
RADC is now supporting our work in stereo vision to automate stereo mapping,
relevant to DMA activities.  The image analysis community is actively
interested in IU and AI.
Japanese companies have pursued robotics as part of increasing productivity
in manufacturing.    Intelligent
systems have potential applications in industry in advanced computer-aided
design and  computer-aided manufacturing  (CAD/CAM), especially  geometric
modeling and  geometric  reasoning  in  design,  and  expert  systems  for
manufacturing. 

\F2\CRESEARCH PROGRAM

\F0\JWe carry out research in sensing and perception, in planning,
and in execution of actions.  
In perception, planning, and execution of actions,
we focus on  reasoning about the physical world,
which will greatly extend ACRONYM as an intelligent system for Image Understanding.
ACRONYM is unique as an expert system for IU.
We also plan to use ACRONYM in an intelligent, integrated experimental system
for programming robots, and in intelligent computer-aided design.
In visual perception, we
are studying and implementing VLSI hardware image processors.
We have a major effort in automated stereo vision for cartography, related
to problems of Defense Mapping Agency.  We are
investigating  the  navigation of a wheeled mobile robot.

In sensing, we are designing high performance
touch sensors and acoustic ranging sensors. 
In execution mechanisms, we are
making design studies of advanced manipulators and hands,
 and studying dynamics and sensory control.

We have built a geometric reasoning system, ACRONYM, containing a substantial
core of fundamental mechanisms which are powerful and general.  Its performance
demonstrated thus far depends on domain-independent capabilities, not on
special domain-dependent tricks. 

\F2\CVISUAL PERCEPTION

The Stanford AI Lab has a major program in Image Understanding:

\j⊗  ACRONYM integrated vision system:  ACRONYM combines geometric modeling with
      geometric reasoning in the form of a rule-based system; ACRONYM integrates
      interpretation with stereo vision and ranging, and includes edge-based segmentation.\.

\j⊗  stereo vision;\.

\j⊗  segmentation and edge operators;\.

\j⊗  VLSI implementation of vision operations.\.

Stereo

\J
We have developed a sequence of mechanisms of increasing power
for incorporating geometric constraints for automating stereo mapping.
[Baker 82] describes the most recent system.
In support of research on stereo vision, a survey of stereo vision systems
and supporting vision technology was conducted.  Thus, the
scope of the study was very broad [Binford 82c]. 
We are working to build an advanced stereo system integrating constraints
at all levels in a rule-based system.\.

\JAn improved segmentation system
is under construction [Marimont 82].  It has several
components, edge finding based on lateral inhibition, curve linking,
curve segmentation, and grouping.  The edge finding module 
removes the effects of smooth shading.  
Edges are localized to subpixel accuracy [Binford 81].
Curves are segmented into curve elements, as cubic splines.
The grouping of curves into extended regions is underway.
It is based on a few fundamental operations including continuity of curves
and translational invariance from [Nevatia 74].\.

\JWe are conducting research to build a fundamental underpinning for mechanisms
of ribbon finding and related grouping operations.  Now ACRONYM matches single
ribbons, then pairs of ribbons.  This process is combinatorial.  Pairing of edges
in ribbons allows many potential combinations, e.g. lanes of a highway.  We 
seek to cut these combinatorics of matching by selecting groups to match which
are well-chosen.
 One aspect of the problem is determining what image
structures provide evidence of objects in three-space.  
This is related to the classical figure/ground problem.  It is considered
as an extension
of inference rules for interpreting images as surfaces [Binford 81].  Ribbons
are an example of area structures; they appear as projections of generalized 
cylinders.   Junctions or stars composed of curves or of ribbons are another 
class of image structures.  Even though the rules with vertices have wide
application and considerable generality, new results are expected to apply
in a much broader class of cases [Binford 82b].  Another aspect is locating
regularities in images without relating them to surface interpretations [Lowe 82].
The principle that the world perceived should be independent of the observer
leads to scale invariance in addition to position and rotation invariance.
This implies that grouping operations should be performed at all positions,
all orientations if directional, and all scales.  Structures can occur at
multiple levels; in the ocean, for example, the water surface is described by
ripples and eddies superimposed on waves at one scale,
described as flat at a larger scale, and circular at the scale of the
earth.  The principle that allowable computational complexity is limited
implies that only the lowest complexity grouping operations can be carried
out.  In particular, complexity linear in the number of features implies
grouping of each element with a constant number of other elements.
Here we intend grouping by proximity and neighborhood relations.
Diameter-limited grouping is not effective here; what is appropriate is
complexity-limited grouping up to the limit of number of neighbors.

A measure is defined of the likelihood of random occurrence of constellations,
using non-parametric statistics, without a priori knowledge of distributions.  
An example is described of determining linear features in dot patterns.\.

\F0\CVLSI hardware

\JWe are extending our study and implementation of integrated circuit (VLSI)
parallel hardware architectures for computer vision.  
A key problem in machine vision is implementing vision algorithms
in real time, i.e. fast enough to be useful in applications.
[Miller 82b] describe architecture studies aimed at development of
an array of 128x128 bit-serial general purpose processors in wafer scale
integration.  There is a large probability that some of the processors
will be faulty.
Such a large circuit requires fault tolerant design.  They demonstrate
an algorithm for connecting the array around defective processors, an algorithm
effective for up to 10% defective processors.  They describe
software experiments used to explore issues of architecture.
Previously, [Miller 81] designed, implemented, and tested one working element of
the array.

We have surveyed hardware implementation of 
vision algorithms, a review which is expected to be published. 
As a summary of the state of the art,  most processors
are too special purpose to have long term interest (e.g. binary algorithms).
The most interesting general purpose processors
are the MPP of NASA-Godard. and the CLIP-IV.  Some special purpose processors
are the Hughes RADIUS processor, systolic processors which require a special
design for each algorithm, and the MIT zero-crossing convolution board.\.

\F2\CREASONING ABOUT THE PHYSICAL WORLD

\F0\CLearning

\JWe are introducing structural learning mechanisms into ACRONYM.  
We want ACRONYM to learn object models and object classes, to learn 
rules and strategies, i.e. programs, and to use what it has learned.
We want it to reason that being white is not important to being a cup
while having a handle may be important.
Building the knowledge base required for robotics and vision  or
building rule bases which capture the knowledge of experts can
consume great effort.

Reasoning by analogy provides 
one mechanism to use what has been learned.
To achieve a goal state from an initial state, consider actions similar to
actions which achieved similar goal states from similar initial states.
The key issue is defining similar actions, similar goals and similar initial
states, all in ways that are selective.  A similarity is defined by an 
equivalence class in a representation.  For example, in the 
monkeys and bananas problem, 
if the system can abstract goal state and initial state as similar to points 
or vectors, the system might already have a solution, namely translation.
If there were no translation defined in three space, it could be defined
by analogy from translations in two space.
Points in three space are similar to points in two space under projection.

Thus representation is a central issue in defining similarity classes of
objects.  We have argued that fundamental definitions of object classes
are functional [Binford 82], that function = form. 
Function is represented by structure in space/time.   Thus, representation
of object classes is representation of function is representation of abstract
form.   An essential part of learning is relating 
function and structure.  We have collaborated with MIT on learning production
rules by combining geometry in ACRONYM and work
relating function and structure at Stanford with work at MIT on learning by 
analogy and a natural language input system.  Two papers are forthcoming.

We are concerned with learning from one example or few, because it is difficult
to present large sets of examples.
We are crucially concerned with learning causal relations in distinction to
statistical correlations, because causal relations define decision
criteria which are dependable.  In contrast, decisions based on
statistical distributions are often unreliable because of systematic
bias.  It is quite difficult to avoid bias in selecting samples of data.\.

\,
\CRepresentation

\JA major part of the ACRONYM effort is building a solid representation
base for reasoning, including
representations of physical phenomena, object classes, space/time.
Models should be clear and intuitively simple so that researchers can understand
them; models should be powerful so that they can be used widely.
We want to build models and specify tasks in a simple, natural way at a high level
including learning from examples.

We will represent physics in ACRONYM.
We make an identification between physical structures and
geometric structures, e.g. representing positions as vectors,
and an identification between physical actions and geometric maps, e.g.
rotations as orthogonal transformations. 
We will model kinematics and dynamics, plus perhaps other phenomena (physical 
optics).
We plan to model observation and experimentation for all sensory modes.
For example, for vision we will model illumination and sensors.
These models will relate observations to geometric constraints.

\JWe will build a task specification language for ACRONYM.
We define a task as a sequence of partially-specified initial states and goals,
plus possible partially-specified actions to reach the goal. 
States are specified in space-time.
Tasks may be specified explicitly or implicitly (procedural or declarative).

We are extending representation of space/time in ACRONYM.
 The representation of time
makes use of the same mechanisms as the representation of space.
The representation of time assumes events and an observer
with an internal clock, i.e. a mechanism for judging before and after, with
an internal metric.  Semantically related clusters of events 
have local time frames [Malik 82].  Coordinate transformations relate time frames.
Events may be continuous or discrete. 
Parallelism and synchronization are represented by constraints.
Thus, the ACRONYM constraint manipulation system provides most of the
mechanism for representing and manipulating constraints. 
Constraints are linear symbolic expressions with variables.  Constraint
resolution becomes a linear programming problem which is solved by
a simplex algorithm.  The method of testing satisfiability of constraints 
is complete.  Upper and lower bounds can be determined.  
Space and time can be considered together.

We are extending mechanisms for representation of form.
We will define and implement combined surface and volume representations
as an extension of generalized cylinders.
We will extend generalized cylinders for completeness, i.e. to span very 
large classes of objects, defining spline representations of generalized
cylinders which can be pieced together to approximate arbitrary shapes.
We will  extend the formal definition of generalized cylinders; we
intend to collaborate with Brady of MIT in parts of this effort.
We will extend algorithms for deriving generalized cylinder descriptions 
from data.  

\,
\CGeometric Reasoning

\F0\JWe are extending  past work on general mechanisms for recognition.
A useful paradigm for recognition is that I recognize a friend
after ten years have passed, when he has gained twenty pounds and lost his
hair, has aged considerably and is wearing different clothes.
Usual paradigms of identification are inadequate, e.g. graph endomorphisms or
fixed template-matching (matched-filtering) with a distance function.
We plan to extend work on indexing, i.e. efficient means for recognizing
complex objects. 

We will extend research on monocular cues to object interpretation
and figure/ground discrimination.
Instead, it is important to group image features in canonical ways.  Two
related approaches emerge.  Some image features suggest three dimensional
structure, other image features suggest image
structures without clear three-dimensional structure.  These groupings
are related to figure/ground perception.

Recent theoretical results outline a general theory of interpretation of 
line drawings which promises to include arbitrary numbers of curved surfaces
with surface markings and shadows, paper (non-solids), cracks, and wires
[Binford 81]. These results suggest general rules for inferring whether
surfaces are planar, or if not planar, for inferring their curvature.
Results also show effective means for using shadows as human interpreters do
[Lowe 81]. [Lowe 82] and [Binford 82b] extend this analysis to the figure/ground
problem in grouping image curves into objects, in forming ribbons
and groups of ribbons. They also present preliminary results in finding clusters
of dots, edges, and texture elements.  Other results show geometric constraints on 
stereo correspondence of edges and surfaces, and constraints on occlusion
[Arnold 80].  The rules encompass individual constraints and constraints
on distributions.  Inference rules include: zeroth order continuity (obscuration);
first order continuity (continuity of tangent plane); surface curvature;
principle curvatures; surface orientation; stereo; edge orientation and curvature;
shadows and illumination.\.

\CRESEARCH PROGRAM IN ROBOTICS

\F0\JThe Robotics Laboratory carries out a broad research program in computer vision
and manipulation, including:\.

\j⊗  design: design of a three finger hand; design of advanced manipulators;\.

\j⊗  dynamics and control of manipulators: multiple, cooperating manipulators;
      end point sensing and visual tracking; adaptive control;\.

\j⊗  task level force sensory control: sensor technology; interfacing;
      analysis of force strategies; high level language for force control;
      teaching force strategies;\.

\j⊗  programming systems for programmable assembly: the AL system has an interpreter,
        force control, source language debugging; graphics for debugging and experimentation
      with force control;\.

\j⊗   next generation of programming systems for robots:  geometric modeling 
      with geometric reasoning;
      offline programming; integrating sensing and vision;\.

\j⊗  inspection: development of an intermediate level industrial vision system with
      less sensitivity to lighting, greater discrimination of shape, however 2D;
    discrimination of essential from cosmetic flaws;\.

\F0\CSensor Technology

\JResearch in visual perception is described separately.
We collaborate with groups at Stanford, Honeywell, and elsewhere
in development  of touch sensors for robot  hands.
We also plan to collaborate on acoustic imaging to be used  in
depth ranging for a mobile robot and for proximity sensors for robot  hands.
We will cooperate in use of piezoelectric materials. 
In the past, we have experimented extensively
with touch sensing [Binford 72]  and developed the Scheinman force  sensor
which has  been widely  distributed. 

\F2\CPLANNING AND DECISION MAKING

\F0\CIntelligent Experimental System

\JPreviously, we developed the AL system for programming robots, and developed an
integrated experimental robotics system based on AL.
We are working to  integrate all our vision  and robotics capabilities, including
AL, in ACRONYM to form a unique intelligent experimental system.\.

\CIntelligent Robots: Programming
 
\JHow do we program robots and programmable devices?  We developed the  AL
programming system for robots, then made  a portable version.  

We  will
extend  AL's  communication  capabilities  for  distributed  systems,   its
mechanisms for  synchronization, and  its  mechanisms for  error  recovery
(exception  handling).   We  will   introduce  new  mechanisms  for   user
interface.   There  are  three  other  implementations  based  on  AL,  at
Karlsruhe, Tokyo Univ, and Univ of  Grenoble.  The AML language of IBM  is
comparable to AL but AL is  portable and device independent, while AML  is
neither.  There are a  number of other  languages under development  which
are subsets of AL and not so fully implemented.

We plan to develop a next  generation robot programming language  based
on geometric  reasoning in  ACRONYYM,  with geometric  modeling, use  of  a
computer-aided design data base, planning and problem solving,  mechanisms
for integration of  vision and  other sensing,  off-line programming  with
simulation,  and   a   hierarchy   of  language   and   computer   systems
(maxi,mini,micro).  We will automate choice of grasping positions,  extend
collision  avoidance,  investigate  automating  the  use  of  sensing   in
verification of  robot actions,  and automate  translation of  constraints
into positions  and forces  in parts  mating.   We made  a rule  base  for
automated grasping in  1979.  Comparable  work includes  AUTOPASS of  IBM,
and RAPT at Edinburgh.\.

\CIntelligent Design

\JWe study  intelligent systems  for  computer-aided  mechanical
design,  based  on   the  ACRONYM   system.  CAD  as   now  practiced   is
computer-aided drafting and archiving.  The prominent function is computer
graphics to show views of objects.  We are concerned with creative design.
An objective is a fast  turnaround prototyping fabrication facility.   One
of  our  main  functions  will  be  symbolic  manipulation  of   geometric
quantities including  symbolic mathematical  expressions.  We  will  study
design for  assembly, especially  manufacturability including  tolerancing
and symbolic propagation of  tolerance distributions, and automated  parts
classification  for  group  technology.    We  will  study  synthesis   of
mechanical designs using the specification of design constraints in  terms
of function and  the relation  of function  to structure  [Lowry 82],  and
methods  of   testing  constraint   satisfaction.    We  will   also   use
optimization, simulation,  and  least  squares  solutions  to  systems  of
equations which are generated  automatically by instantiating  constraints
[Lowe 80].  We are aware of no equivalent work.  Work on CAD at  McDonnell
Douglas, GM, IBM, Univ of Rochester,  Cornell, Univ of Tokyo, Berlin,  and
Stuttgart represent  advanced  development  of traditional  directions  in
CAD.\.

  precision machining

We are collaborating on a program of expert systems for precision machining.
One part of the effort is modeling thermal and other error effects to
automate compensation.  Another part is to automate the knowledge of
expert machine operators who often carry a lore which really makes 
precision machines function.

\F2\CEXECUTION

\F0\CMechanical Design

\JHow do we build hands and arms which can make secure grasps, use  tools,
or exert delicate forces for assembly?  

We collaborate with  Prof.
Roth and with MIT on design studies of advanced hands and manipulators for
force control  and  compliance.  Robots  are  now primarily  designed  for
position control; there  is no theory  for their design  in dynamic  force
control.  We will make parametric analysis and experimentation to  provide
quantitative models for design optimization.  Based on past record,
we think that we can contribute to a collaboration.
Most hands have  two
parallel jaws; a third finger adds  torque for secure grasps, particularly of
irregular surfaces.  Hands can provide fine  motion for precision  sensory
control.

We designed  and  built  the  Scheinman  Stanford  arm  in  1970  and  the
Stanford-JPL three finger hand [Salisbury 81].  Both have had  significant
impact outside Stanford;  several laboratories  are buying  copies of  the
Stanford-JPL hand.   The Salisbury  hand and  Okada's hand  at ETL,  Japan
represent the  state of  the art.   MIT  and the  University of  Utah  are
designing an advanced hand.  Direct-drive arms of Asada and Kanade at CMU,
Asada at MIT, and a similar arm by Hasegawa at ETL, Japan, lead the  state
of the art in manipulators.  Unimation  is building a similar arm.   Where
possible  we   plan  to   collaborate  with   these  efforts   and   avoid
duplication.\.

\CDynamics and Sensory Control

\JHow do we control complex, multi-degree  of freedom devices?  How do  we
control hands and arms to  exert delicate forces?  How  do we use arms  to
full efficiency, i.e. move loads as rapidly and smoothly as possible  under
sensor control?   

We have  made  a sophisticated  theory  for  coupled
control of the three finger hand using tension sensors [Salisbury 81];  we
are now implementing the theory in order to experiment and extend it.  The
hand has three fingers,  each with three degrees  of freedom.  We  command
the position, velocity and  internal force on an  object to be grasped  by
the hand, rather than command individual motors for nine joints.  The same
analysis is  relevant  for  two  arms cooperating  or  other  closed  loop
kinematic chains.  We  will control  two arms  cooperating in  assemblies.
The work of [Salisbury  81] is the most  sophisticated work in control  of
closed loop kinematic chains.

We have begun to investigate  high  performance  adaptive  control  of
manipulators based  on historical  and real-time  estimation of  friction,
mass and inertias of manipulators and their loads.  The essential  problem
is efficient  estimation  of  dynamic properties..   Some work on estimation has been
done by Goor of GM, and Muhamed of CEA.  Work  in adaptive  control has
been led  by  Linkoping  Univ,  Sweden,  Franklin,  Craig  and  others  at
Stanford, Various researchers have contributed
to efficient  calculation  of dynamics  of  robots assuming  that  dymamic
parameters  are  known,  including  Luh  of  Purdue,  Hollerbach  of  MIT,
Featherstone of Edinburgh, Orin  of Ohio State  Univ, Khatib at  Stanford,
Renaud at Toulouse, and Vukobratovic.

In the past we implemented compliance and force control based on
a general analysis [Salisbury 80].  We  will extend that analysis to  deal
with problems of damping.  We  are especially concerned with this  problem
of constrained  motion  in  parts  mating,  and  developing  parts  mating
strategies.  We will  investigate mating  of compliant  parts.  The  force
control algorithm of Salisbury represents the state of the art; Whitney at
Draper has contributed  to passive compliance  and force control.   Draper
has contributed the fundamental analyses  of parts mating and are  working
in mating of elastic parts.

   We have  implemented a Cartesian  force control system,  which will  be
extended greatly.  The  Cartesian system  facilitates real-time  collision
avoidance.  We will soon demonstrate real-time collision avoidance of  two
manipulators working  in  the same  space.   The Cartesian  force  control
system has  no known  rivals.  Only  the proposed  collision avoidance  is
real-time or  has  promise  of real-time  performance  in  the  forseeable
future.  Collision avoidance has been investigated by Widdoes at Stanford.
Methods of  Udupa at  Caltech and  Lozano-Perez  at MIT  are based  on  an
approach similar to that of Widdoes.\.

\CMobile Robot

\JWe are about to acquire  a mobile  robot  to continue  a long  tradition  of
studies of navigation of mobile robots [Schmidt 72, Moravec 80].  There is
a near-term  objective  of  making  a  robot  which  navigates  in  simple
environments using acoustic sensors.   We will collaborate with  Unimation
which plans to develop a product based on such a mobile robot. 

We plan development of a robot which builds its own model of a  changing
environment, which  has  high  performance  acoustic  imaging  and  stereo
vision, and which has intelligent task planning.  Comparable work has been
initiated at CMU by Moravec; substantial  research is done at Toulouse  on
the mobile robot Hilare, at Naval Ocean Systems Center (NOSC), San  Diego,
on undersea mobile  robots, and  by Westinghouse Naval  Systems.  We  will
collaborate with Unimation and where possible, with NOSC and others.\.

\,
\F2\CACCOMPLISHMENTS

\F0\JStanford leads by far in producing robotics leaders.
The Robotics Laboratory has traditionally attracted many highly-talented
students who form a major part of our research effort.   Most of the
education process has been one-to-one in research supervision, but we
have offered a course in robotics since 1971.  It has expanded to a three
quarter series.

Research has concentrated on two major systems, AL for programming robots,
and ACRONYM.

A user should program ACRONYM in terms of geometric models and geometric
task specifications, a common language natural to both user and ACRONYM.
 ACRONYM constructs perceptual programs to 
carry out the assigned task.   ACRONYM should have a general core
plus mechanisms to use problem-specific information.\.

\JACRONYM has been demonstrated successful on a few images of aircraft in 
aerial images.  
Figure 1 shows an example with high resolution. 
A rule base has been built in ACRONYM for automated
choice of grasp points.  It has been used for a robot simulator.

In a real sense, ACRONYM reasons from first principles.
ACRONYM has a general core in that its rules implement algebra and projective
geometry.  There are no special rules for aerial images or aircraft. 
ACRONYM has viewpoint-independent three-dimensional
object models in the form of part/whole graphs, in terms of generalized cylinder
primitives.  ACRONYM represents object classes, for which subclasses and
specific objects are represented as restrictions by constraints
in the form of symbolic expressions with numeric type.

ACRONYM searches for instances of models in images.
It employs geometric reasoning in the form of a rule-based problem-solving 
system.  Geometry is the key, while the rule-based
system is simply a way of implementing geometry.
ACRONYM predicts appearances of models
in terms of ribbons and ellipses.  It uses an edge finder to make observations of
ribbons and ellipses in images. 
ACRONYM finds observed ribbons consistent with predicted ribbons, 
and restricts interpretations to those which are parts of clusters consistent with predicted
structures of ribbons.
It interprets in three dimensions by enforcing constraints of the three 
dimensional model.
Thus, to identify aircraft, it matches observed ribbons to predicted
ribbons for wings and fuselage, then finds clusters of ribbons which are
consistent with combined wings and fuselage of a three-dimensional aircraft
model.\.

\JACRONYM makes predictions which are viewpoint-insensitive, 
in the form of symbolic constraint expressions with variables.  One mechanism of
viewpoint-insensitive prediction is the use of observables which are
invariant and quasi-invariant over large ranges of viewing angle.
ACRONYM does not generate all possible views of an object. Total prediction 
has combinatorial complexity.  For a polyhedron with n distinct faces, there are
2∩n views.  Instead, ACRONYM predicts partial views for individual faces, of which
there are of order n. 
The image shape descriptors are invariant under image rotation.\.

\JInterpretation proceeds by combining local matches of ribbons into clusters.
Global interpretations must be consistent in two ways: First, they must 
satisfy constraints specified by the arcs of the prediction graph.  Second,
accumulated constraints that each local match imposes on the three dimensional model
must be satisfiable.  The interpreter searches for maximal subgraphs of the
observation graph which are consistent with constraints of subgraphs of the
prediction graph.  Each such match is an interpretation graph.  The interpreter
matches ribbons against predictions of ribbons.  It then tries to instantiate
arcs of the prediction graph by checking pairs of regions to see whether they
satisfy relations predicted. For pairs which satisfy image relations,
it merges constraints on the underlying three-dimensional model.

The top-down paradigm is only one part of the ACRONYM design.
We believe that the way to a general vision system lies in spatial
understanding, as contrasted with image understanding. 
We believe that the major part of interpretation is
not at the image level, but at the level of volumes.  Descriptive 
mechanisms which generate volume descriptions are essential, combined with
prediction and interpretation at the level of volumes.
Certainly stereo, motion parallax, and object motion are important
observation capabilities, together with shading.  Recent theoretical work on
monocular interpretation of surfaces from images [Binford 81, Lowe 81]
make it appear promising that general mechanisms for
generating spatial observations from images will be developed soon to
support general vision systems.\.

\,